package day0;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class code3 {

    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);

        int sum = 0;
        int all = 0;
        for (int i = 0; i < nums.length; i++) {
            int req = k-nums[i];
            sum += map.getOrDefault(req,0);
            all += nums[i];
            map.put(all,map.getOrDefault(all,0)+1);
        }
        return sum;
    }


    public int[] maxSlidingWindow(int[] nums, int k) {

        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b) -> a[0]==b[0]?a[1]-b[1]:b[0]-a[0]);
        int[] arr = new int[nums.length-k+1];
        int len = nums.length;
        for(int i=0;i<k-1;i++){
            queue.add(new int[]{nums[i],i});
        }


        for(int i=k-1;i<nums.length;i++){
            queue.add(new int[]{nums[i],i});
            while (queue.peek()[1]<i-k+1){
                queue.poll();
            }
            arr[i-k+1] = queue.peek()[0];
        }

        return arr;
    }

    public String minWindow(String s, String t) {
        if(t.length()>s.length()) return "";
        int len1 = s.length();
        int len2 = t.length();

        HashMap<Character,Integer> map1 = new HashMap<>();
        for (int i = 0; i < len2; i++) {
            char ch = t.charAt(i);
            map1.put(ch,map1.getOrDefault(ch,0)+1);
        }

        StringBuilder sb = new StringBuilder();
        //sb.delete(0,sb.length());
        int lt = 0;
        HashMap<Character,Integer> map2 = new HashMap<>();
        for(int rt=0;rt<len1;rt++){
            char ch = s.charAt(rt);
            map2.put(ch,map2.getOrDefault(ch,0)+1);
            while (fun(map1,map2)){
                if(sb.isEmpty()|| s.substring(lt,rt+1).length()<sb.length()){
                    sb.delete(0,sb.length());
                    sb.append(s, lt, rt+1);
                }
                char tep = s.charAt(lt);
                map2.put(tep,map2.getOrDefault(tep,0)-1);
                lt+=1;
            }
        }

        return sb.toString();







    }

    public boolean fun(HashMap<Character,Integer> map1,HashMap<Character,Integer> map2){
        for(char ch:map1.keySet()){
            if(!map2.containsKey(ch)) return false;
            if(map2.get(ch).compareTo(map1.get(ch))<0) return false;
        }
        return true;
    }


    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length+1];

        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int max = Math.max(dp[i]+nums[i],nums[i]);
            dp[i+1] = max;
            result = Math.max(result,dp[i+1]);
        }

        return result;




    }



}
